1. Field of the Invention
The present invention relates to pattern comparators designed to perform parallel pattern comparisons on real-time data.
2. Description of the Related Art
Pattern comparators have been developed which use fuzzy logic and parallel processing to perform pattern comparisons on multiple real-time data streams in parallel. Such pattern comparators are effective in applications where inaccurate or noisy data may be present. Such applications include recognition systems (for example, object, character, voice, fingerprint, currency, etc.), security and remote surveillance, CAM (computer-aided manufacturing) systems, robotic control systems and rapid data base search/retrieval systems.
It was recognized that pattern comparators could be implemented using fuzzy logic, developed by L. Zadeh in 1963. Rather than evaluating the two values "TRUE" and "FALSE" as in digital logic, fuzzy terms admit to degrees of membership in multiple sets so that fuzzy rules may have a continuous, rather than step-wise, range of truth of possibility. For example, in applying fuzzy logic, a person need not strictly be included or excluded as a member from a set of "tall persons"; rather, to the extent a person may be "tall" to a greater or lesser degree, the member is assigned to the set with a degree of membership between the values of "1" and "0".
A pattern comparator implementing fuzzy logic was developed by Micro Devices, Lake Mary, Fla., known as the MD1210A Fuzzy Set Comparator. The MD1210A functionally had an implementation resembling the block diagram shown in FIG. 1. FIG. 1 shows a pattern comparator 10 which compares serial input data to stored patterns of data in real time. The pattern comparator 10 receives serial input data (SERIAL DATA IN) least-significant-bit first and latches the data by each bit-field into a flip-flop 12 on the falling edge of a CLOCK signal. A bit-field is defined as a stream of data bits up to eight bits, the last bit being the most significant bit. The bit-field is output to an array of magnitude comparators 14 which compare the bit-field with a plurality of predetermined pattern data (PATTERN DATA 0-7). The pattern data may be stored, for example, in external memory such as Pattern RAM (not shown). The magnitude comparators perform the pattern comparison either by Hamming or Linear Distance metrics, selectable by the user.
The comparison of the bit-field with each of the input pattern data 0-7 in the corresponding magnitude comparator 14 results in a corresponding error, or distance value, between the bit-field and the corresponding pattern data. This distance value represents how "far" the pattern data is from the bit-field, for example a distance value of zero (0) indicates that the pattern data and the bit-field are an exact match.
The distance value for each pattern data 0-7 is stored and accumulated in an accumulator 16. The comparison is repeated a predetermined number of times, one bit-field at a time, with the pattern data stored in the external pattern memories, and the resulting distance values are accumulated in the accumulators 16.
After the comparison for the bit-fields has been performed the predetermined number of times, each accumulator contains a sixteen bit accumulated distance value for the corresponding pattern data. The accumulated distance values for the corresponding pattern data are input to a neural network 18. The neural network 18 compares the set of accumulation of distance values to determine the minimum accumulated distance value. The accumulated distance values are also compared to a predetermined threshold value, representing the acceptable degree of fuzziness permitted. In other words, if the pattern data must have a sufficient degree of correlation to the bit-field to constitute an acceptable recognition, the threshold value defines the maximum distance value permitted. The comparison to the threshold (not shown in FIG. 1) can be made either before each of the accumulated distance values are compared, or after a minimum accumulated distance value is determined. If the minimum accumulated distance value is also less than the predetermined threshold, then a best match is deemed found between the bit-field of the input serial data and the stored pattern data. The pattern data from the pattern data set 0-7 having the best match is identified by the output WINNER, and the minimum accumulated distance value which corresponds to the pattern data deemed a best match is output to an EBUS OUT terminal to compete with any other pattern comparator devices coupled to an expansion bus (not shown).
As shown above, the pattern comparators use a predetermined threshold to determine the acceptable degree of fuzziness permitted, e.g., the maximum distance value permitted. Although this design is acceptable for character recognition in a static environment, it is unacceptable in a dynamic environment because patterns may be changing in real time.
Specifically, it is desirable to maintain image recognition performance even when a background of the image may be changing over time. For example, it is desirable to be able to track a missile while the background of the missile changes due to sun, clouds, etc.; also, it is desirable in surveillance applications that humans can be detected while discriminating them from animals over different light and weather conditions. Although one could attempt to compensate for changes over time by providing successive modifications of reference patterns, such modifications could eventually result in erroneous detections.
Finally, in applications where one is unable to determine an adequate threshold, it is desirable to have a system where the threshold can be automatically determined and then automatically updated depending on the input conditions.
The MD1210A by Micro Devices also had a neural network 18 which performed rapid comparison of the accumulated distance values. Highly parallel architectures which perform faster processing speeds were proposed by Lippman (1987). However, the relatively large number of parallel connections in the neural net increases the size of an IC chip, and thus increases the overall cost of the system.
It would be desirable to provide a neural network-type arrangement which was specifically implemented for pattern recognition. Specifically, it would be advantageous to not only use the neural network-type arrangement to quickly determine the minimum accumulated distance value, but also to quickly identify during the pattern comparison which of the pattern data are likely candidates as the best match to the input bit-field. In addition, if multiple pattern comparators are coupled to an expansion bus to increase pattern comparisons, it would be desirable for each neural network to be able to increase processing speed by disengaging pattern comparators deemed not to be candidates to provide the best fit pattern data. Finally, it would be desirable if the neural network-type arrangement was implemented to minimize the amount of area used on an IC chip, thereby minimizing the overall cost of the IC chip.